package com.wfp.kmp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Auther: 14029
 * @Date: 2018/6/5 20:20
 * @Description: KMP算法，只回溯模式串，不会回溯主串
 */
public class KMPAlgorithm {

    /**
     * 获得部分匹配表 ---普通版
     * @param str
     * @return
     */
    public static int [] getNext(String str){
        char[] strs = str.toCharArray();
        int[] next = new int[strs.length];
        next[0] = -1;

        int j = 0;
        int k = -1;
        while (j<strs.length-1) {
            if (k == -1 || strs[j] == strs[k]) {
                j++;
                k++;
                next[j] = k;
            }else {
                k = next[k];
            }
        }
        System.out.println("模式串部分匹配表：");
        Arrays.stream(next).forEach((x)->{
            System.out.print(x + "  ");
        });
        System.out.println("");
        return next;
    }

    /**
     * 获得部分匹配表 ---升级版本
     * @param str
     * @return
     */
    public static int [] getNextUpgrade(String str){
        char[] strs = str.toCharArray();
        int[] next = new int[strs.length];
        next[0] = -1;

        int j = 0;
        int k = -1;
        while (j<strs.length-1) {
            if (k == -1 || strs[j] == strs[k]) {
                //普通版的不同点
                if(strs[++j] == strs[++k]){
                    next[j]=next[k];
                }else {
                    next[j]=k;
                }
            }else {
                k = next[k];
            }
        }
        System.out.println("模式串部分匹配表：");
        Arrays.stream(next).forEach((x)->{
            System.out.print(x + "  ");
        });
        System.out.println("");
        return next;
    }


    /**
     * 找出模式串在主串中第一次出现的位置
     * @param str1 主串
     * @param str2 模式串
     * @return 第一次出现的位置
     */
    public int findFirstPlace(String str1,String str2){
        int i=0;
        int j=0;
        //获得部分匹配表
        int[] next = KMPAlgorithm.getNext(str2);
        while (i < str1.length() && j < str2.length()) {
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                //根据next数组的指示j进行回溯，而i永远不会回溯
                j = next[j];
            }
        }
        if (j == str2.length()) {
            return i-j;
        } else {
            return -1;
        }
    }

    /**
     * 2.	找出子串在主串中所有出现的位置
     * @param str1 主串
     * @param str2 模式串
     * @return 所有出现的位置
     */
    public List<Integer> findAllPlace(String str1, String str2){
        int i=0;
        int j=0;
        List<Integer> allPlace = new ArrayList<>();

        //获得部分匹配表
        int[] next = KMPAlgorithm.getNext(str2);

        while (i<str1.length()){
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                //根据next数组的指示j进行回溯，而i永远不会回溯
                j = next[j];
            }
            if (j == str2.length()) {
                allPlace.add(i-j);
                j=0;
            }
        }

        return allPlace.isEmpty()?null:allPlace;
    }

    /**
     * 3.	将主串中所含的所有子串替换成replaceStr
     * @param str1 主串
     * @param str2 模式串
     * @param replaceStr 需要替换的串
     * @return 替换后的主串
     */
    public String  replaceAll(String str1,String str2,String replaceStr){
        int i=0;
        int j=0;

        //获得部分匹配表
        int[] next = KMPAlgorithm.getNext(str2);

        while (i<str1.length()){
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                //根据next数组的指示j进行回溯，而i永远不会回溯
                j = next[j];
            }
            if (j == str2.length()) {
                String startStr = str1.substring(0, i-j);
                String endStr = str1.substring(i,str1.length());
                str1 = startStr+replaceStr+endStr;
                i = i+replaceStr.length()-str2.length();
                j = 0;
            }
        }

        return str1;
    }
}

